#include "QuadTree.h"
QuadTree::QuadTree(const CollisionEntityRectangle &rect, int current_deep, int objects_max, int deep_max) : rect(rect), current_deep(current_deep), objects_max(objects_max), deep_max(deep_max)
{
    objects_list = new std::list<CollisionEntity *>();
    nodes_list = new std::vector<QuadTree *>();
    // printf("create size:%d %f %f\n", current_deep, this->rect.getSize().x, this->rect.getSize().y);
}

QuadTree::~QuadTree()
{
    if (nodes_list != nullptr && !nodes_list->empty())
    {
        for (auto it = nodes_list->begin(); it != nodes_list->end();)
        {
            delete *it;
            it = nodes_list->erase(it);
        }
    }
    if (nodes_list != nullptr)
    {
        delete nodes_list;
    }
    if (objects_list != nullptr)
    {
        delete objects_list;
    }
}

void QuadTree::insert(CollisionEntity *shape)
{
    if (shape == nullptr)
    {
        return;
    }
    if (nodes_list != nullptr && !nodes_list->empty())
    {
        int index = getInsertIndex(shape);
        if (index != -1)
        {
            nodes_list->at(index)->insert(shape);
            return;
        }
    }
    objects_list->push_back(shape);
    shape->layer=current_deep;
    if (objects_list->size() >= objects_max && current_deep < deep_max)
    {
        split();
        for (auto it = objects_list->begin(); it != objects_list->end();)
        {
            CollisionEntity *s = *it;
            int index = getInsertIndex(s);
            if (index != -1)
            {
                nodes_list->at(index)->insert(s);
                it = objects_list->erase(it);
            }
            else
            {
                it++;
            }
        }
        return;
    }
}

void QuadTree::clear()
{
    if (nodes_list != nullptr && !nodes_list->empty())
    {
        for (auto it = nodes_list->begin(); it != nodes_list->end();)
        {
            delete *it;
            it = nodes_list->erase(it);
        }
    }
    objects_list->clear();
}

int QuadTree::getInsertIndex(CollisionEntity *entity) const
{
    if (nodes_list->empty())
    {
        return -1;
    }
    int i = 0;
    for (i = 0; i < 4; ++i)
    {
        if (nodes_list->at(i)->rect.contain(entity))
        {
            return i;
        }
    }
    if (i >= 4)
    {
        return -1;
    }
}

void QuadTree::split()
{
    if (nodes_list == nullptr)
    {
        nodes_list = new std::vector<QuadTree *>();
    }
    if (!nodes_list->empty())
    {
        return;
    }
    Vector2 subsize = rect.getSize() / 2;
    Vector2 pos[4];
    pos[0] = rect.getPosition();
    pos[1] = rect.getPosition() + Vector2(subsize.x, 0);
    pos[2] = rect.getPosition() + Vector2(subsize.x, subsize.y);
    pos[3] = rect.getPosition() + Vector2(0, subsize.y);
    if (nodes_list->empty())
    {
        for (int i = 0; i < 4; i++)
        {
            CollisionEntityRectangle subrect(subsize);
            subrect.updatePosition(pos[i]);
            nodes_list->push_back(new QuadTree(subrect, current_deep + 1, objects_max, deep_max));
        }
    }
}

std::list<CollisionEntity *> *QuadTree::retrieve(CollisionEntity *shape, std::list<CollisionEntity *> *retrieveObjects_list) const
{
    if (shape == nullptr)
    {
        return nullptr;
    }
    if (retrieveObjects_list == nullptr)
    {
        retrieveObjects_list = new std::list<CollisionEntity *>();
    }
    if (nodes_list != nullptr && !nodes_list->empty())
    {
        int index = getInsertIndex(shape);
        if (index != -1)
        {
            nodes_list->at(index)->retrieve(shape, retrieveObjects_list);
        }
    }
    for (auto it = objects_list->begin(); it != objects_list->end(); ++it)
    {
        if (*it == shape)
        {
            break;
        }
        retrieveObjects_list->push_back(*it);
    }
    return retrieveObjects_list;
}

std::list<const CollisionEntityRectangle *> *QuadTree::getRectangles(std::list<const CollisionEntityRectangle *> *returnRectangles) const
{
    if (returnRectangles == nullptr)
    {
        returnRectangles = new std::list<const CollisionEntityRectangle *>();
    }
    if (!nodes_list->empty())
    {
        for (int i = 0; i < 4; ++i)
        {
            nodes_list->at(i)->getRectangles(returnRectangles);
        }
    }
    returnRectangles->push_back(&rect);
    return returnRectangles;
}
